package recursion;

/**
 * @Author: Cjj
 * 递归,分治,动态规划,贪心,回溯
 */
public class Recursion {
    /**
     * 动态规划和递归(回溯,分治)
     * 递归和动态规划是从保存过程信息角度划分的。
     *  递归：
     *   作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,
     *   它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题,递归策略只需少量的程序就可描述
     *   出解题过程所需要的多次重复计算,大大地减少了程序的代码量。
     */

    /**
     * 动态规划：
     *  动态规划其实和分治策略是类似的,也是将一个原问题分解为若干个规模较小的子问题,递归的求解这些子问题,然后
     *  合并子问题的解得到原问题的解。
     *
     *  区别：
     *   区别在于这些子问题会有重叠,一个子问题在求解后,可能会再次求解,于是我们想到将这些子问题的解存储起来,当下次
     *   再次求解这个子问题时,直接用就可以。
     *   动态规划所解决的问题是分治策略所解决问题的一个子集,只是这个子集更适合用动态规划来解决从而得到更小的运行时间。
     *   即用动态规划能解决的问题分治策略肯定能解决。
     */

    /**
     * 贪心算法和动态规划
     * 贪心和动态规划是从全局最优角度划分的：
     * 能从局部最优推导出全局最优就是贪心,否则就是动态规划。
     * 贪心算法：
     *  贪心算法中,作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一部之前的最优
     *  解则不作保留。
     *  联系:
     *    动态规划和贪心算法都是一种递推算法
     * 区别：
     * 1.全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解
     * 2.动态规划的关键是状态转移方程,即如何由以求出的局部最优解来推导全局最优解
     * 3.边界条件：即最简单的,可以直接得出的局部最优解。
     */
}
